МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ

ИНСТИТУТ ЭКОНОМИКИ, УПРАВЛЕНИЯ И ПРАВА

Факультет управления

Кафедра «Моделирование в экономике и управлении»

Курс

МАТЕМАТИЧЕСКИЕ МОДЕЛИ В УПРАВЛЕНИИ

Методическое пособие по проведению лабораторных работ

по теме “Линейное программирование”

Лабораторная работа №3

Специальные задачи линейного программирования и их решение средствами Excel

Москва

Введение

Курс “Математические модели в управлении” читается студентам второго курсов дневной и вечерней форм обучения факультета управления по специальностям: 061000 – "Государственное и муниципальное управление", 061100 – "Менеджмент". Курс читается два семестра и охватывает основные темы исследования операций, теории массового обслуживания и теории игр.

Предметом изучения дисциплины “Математические модели в управлении” являются математические модели и методы решения исследования операций, теории массового обслуживания и теории игр.

Цель курса - сформировать у студентов комплекс знаний необходимых для:

· анализа современных проблем в области производства, торговли, финансов, денежного обращения и кредитов;

· оптимальному решению тактических и стратегических задач организационного управления;

Задачи курса научить студентов:

· владеть приемами постановки задач организационного управления;

· на основе описательных задач строить математические модели;

· умению выбрать соответствующий метод решения задачи;

· проведению численных исследований математических моделей;

· умению проведения анализа результатов вычислений;

· умению выбрать наиболее эффективное управляющее решение.

Особенностью программы для студентов факультета управления является:

· рассмотрение актуальных проблем организационного управления в различных структурах – производственных, торговых, финансово – кредитных;

· применение математических методов при анализе и выработки управляющих решений.

Изучив курс, студент:

должен владеть моделями математического программирования, теории игр и массового обслуживания;

уметь использовать математические методы при решении задач организационного управления;

должен уметь использовать в своей работе средства вычислительной техники и современных информационных технологий.

Лабораторные работы призваны, на практике, помочь студентам применить знания полученные на лекциях и при самостоятельной работе. В качестве программной среды используются средства Microsoft Offis Excel (электронные таблицы MS Offis).

Программные средства Excel - Поиск решения является мощным инструментом решения оптимизационных задач. С их помощью можно найти наилучший вариант использования ограниченных ресурсов, обеспечивающий максимальное значение для одних величин, например, прибыли, или же минимальное - для других, например, затрат.

Использования поиска решения поможет дать ответ на такие вопросы:

· Какая цена или ассортимент товаров обеспечат максимальную прибыль?

· Как не выйти за пределы бюджета?

Порядок выполнения работы

На лабораторную работу каждый студент приносит чистую, неиспользованную дискету МД 3,5'. На этой дискете будут содержаться файлы с исходными данными и результатами по всем выполненным работам.

Задание. Получить вариант задачи у преподавателя. Составить математическую модель задачи. Найти оптимальное решение задачи в Excel и показать результаты поиска решения преподавателю на экране компьютера. Отчет составляет на МД.

Отчет. Отчет по лабораторной работе представляется на дискете студента и должен содержать файл с названием ЛР 3 Вариант №… Отчет (Фамилия № группы).

Состав отчета, записанный на МД:

- математическая модель задачи, предъявляемая преподавателю (может быть написана от руки).

- Рабочий лист Excel с исходными данными и математической моделью, протокол решения задачи, куда входят:

- результаты решения в виде отчета Результаты.

Отчет на МД демонстрируется преподавателю на данном лабораторном занятии.

Сдача лабораторной работы преподавателю – при наличии МД с результатами расчета. Во время сдачи лабораторной работы студент должен уметь проводить анализ полученных результатов.

Лабораторная работа № 3.

Тема: Специальные задачи линейного программирования и их решение средствами Excel. К рассматриваемым в пособии задачам относятся задачи целочисленного программирования, экономические задачи, сводимые к транспортной задаче, задача о ранце, задача о закреплении парка самолетов за воздушными линиями и некоторые другие.

Программное обеспечение: Microsoft Excel

Основные сведения

1. Целочисленные задачи линейного программирования.

К задачам целочисленного программирования относятся экстремальные задачи, переменные которых по смыслу задачи могут принимать только целочисленные значения.

Рассмотрим конкретную задачу целочисленного программирования.

Задача.

В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено S кв.м площади. На приобретение оборудования предприятие может израсходовать A руб. при этом оно может купить оборудование n видов. Единица оборудования i-го вида стоит a_i руб. Приобретение оборудования i-го вида позволяет увеличить выпуск продукции в смену на b_i ед. Для установки одного оборудования i-го вида требуется c_i кв.м. площади. Определить сколько единиц оборудования каждого вида необходимо закупить, чтобы максимально увеличить выпуск продукции.

Построение математической модели. Предположим, что предприятие закупит оборудование i-го вида в количестве x_i шт.

Целевая функция задачи описывает увеличение объема выпуска продукции, которое должно быть максимальным, т.е.

F = b₁ x₁ + b₂ x₂ + … + b_n x_n → max.

Запишем теперь ограничения задачи.

Первое ограничение относится к стоимости оборудования и выделенной для этой цели денежных средств:

a₁ x₁ + a₂ x₂ + … + a_n x_n ≤ A.

Второе ограничение относится к размеру площади, которое может быть выделено под оборудование:

c₁ x₁ + c₂ x₂ + … + c_n x_n ≤ S .

По смыслу задачи, количество оборудования может быть только целым и неотрицательным числом:

x_i ≥ 0 и x_i – целые

2. Задачи сводящиеся к транспортной модели

Довольно обширный класс экономических задач, не имеющих ничего общего с транспортной задачей, тем не менее сводится к транспортной модели, и для решения таких задач может быть использован алгоритмы и методы решения транспортных задач (Методическое пособие Лабораторная работа №2. Транспортные задачи и их решение средствами Excel).

В этом случае величины транспортных тарифов имеют различный смысл в зависимости от конкретной экономической задачи, как и величины поставляемых грузов от поставщиков и потребности в них у потребителей.

Рассмотрим конкретную задачу.

Задача. Имеется n участков земли, на которых могут быть засеяны m видов культур. Площадь каждого участка соответственно равна s_i. Каждой i-ой культурой следует засеять площадь v_i . Урожайность каждой из культур для каждого из участков различна и задается матрицей C= {c_ij}.

Определить, сколько гектаров каждой культуры на каждом из участков следует засеять так, чтобы общий сбор зерна был максимальным.

Построение математической модели

Обозначим искомые величины – площадь культуры j засеянной на участке i , как x_ij , i = 1, …, n, j =1, …, m.

Целевая функция представляет собой суммарную урожайность всех культур со всех участков. Так как урожайность культуры j с единицы площади участка i равна с_ij , то урожайность этой культуры с площади x_ij составит с_ij x_ij . Суммарная урожайность – целевая функция, которая должна принимать максимальное значение

.

Ограничения задачи. Поскольку на каждом из трех участков засеиваются все четыре культуры, то сумма площадей занимаемой каждой культурой на каждом участке, должна быть равна имеющейся площади этого участка:

, i = 1, …, n

С другой стороны, суммарная площадь отводимая под каждую культуру, которая засеивается на каждом участке, также должна быть равна заданной площади

, j =1, …, m

Площади культур не могут выражаться отрицательными величинами и потому необходимо выполнение условий:

x_ij ≥ 0, i = 1, …, n, j =1, …, m

Эта модель по ограничениям полностью совпадает с математической моделью транспортной задачи. Модель является сбалансированной.

В данной задаче необходимо максимизировать целевую функцию. Для перехода к стандартной транспортной модели надо заменить функцию F на противоположную функцию F' = – F, которую необходимо минимизировать, т.е.

Далее задача решается известными методами.

3. Задача о ранце

К этому классу задач относятся задачи, в которых необходимо при ограниченных объемах перевозчика и ограничениях по весу, перевезти как можно больше груза или, как можно больше значимого груза. Причем загружаться могут несколько грузов каждого вида.

Рассмотрим конкретную задачу.

Задача.

Морское судно грузоподъемностью M тыс. т. и вместимостью V тыс куб.м. может быть использовано для перевозки n видов неделимых грузов, имеющих массу m_i, объем v_i и стоимость c_i.

Определить, сколько единиц груза каждого вида следует загрузить на судно, чтобы суммарная стоимость груза была максимальной и выполнялись ограничения по вместимости и грузоподъемности судна.

Построение математической модели.

Обозначим через x_i количество единиц i-го груза загружаемого на судно. Целевая функция, выражающая суммарную стоимость груза на судне, будет равна:

.

Ограничения задачи диктуются ограничением на грузоподъемность судна

и ограничением на вместимость судна

Количество единиц грузов не может быть отрицательным и дробным, т.к. все грузы неделимы, поэтому

x_i ≥ 0, целые, i = 1, …, n

4. Закрепление самолетов за воздушными линиями

В задачах этого типа выбирается оптимальный вариант закрепления самолетов различного типа за несколькими воздушными линиями, обеспечивающий минимальные общие затраты при удовлетворении требуемых перевозок.

Задача.

В аэропорту для перевозки пассажиров по n маршрутам может быть использовано m типов самолетов. Вместимость самолета i-го типа равна a_i человек, а количество пассажиров, перевозимых по j-му маршруту за сезон, составляет b_j человек. Затраты связанные с использованием самолета i-го типа на j-ом маршруте, составляют c_ij руб.

Определить сколько самолетов каждого типа и на каком маршруте следует использовать, чтобы удовлетворить потребности в перевозках при наименьших общих затратах, если известно, что количество самолетов i-го типа равно m_i.

Математическая модель.

Обозначим через x_ij – количество самолетов i-го типа на j-ом маршруте. Целевая функция имеет вид

.

Ограничения по количеству самолетов каждого i-го типа

,

ограничения по количеству пассажиров перевозимых по каждому j-му маршруту

Поскольку количество самолетов не может быть дробным, то вводятся следующие ограничения

x_ij ≥ 0, i = 1, …, m, j =1, …, n.

Решение задач средствами Excel.

Приведенные типы задач решаются средствами Excel также как и обычные задачи линейного программирования, включая и транспортные задачи, за одним исключением: если переменные по смыслу задачи могут принимать только целочисленные значения, то в ограничениях, задаваемых в диалоговом окне Поиск решения, необходимо указать, что переменные имеют целочисленные значения.

Для этого необходимо нажать в окне Поиск решения кнопку Добавить (добавить ограничения) и в открывшемся диалоговом окне Добавление ограничения в левом поле занести ячейки с изменяемыми переменными, а в среднем поле, нажать на среднюю кнопку и выбрать в предложенных видах ограничений требование целочисленности (рис. 1). Дальнейший алгоритм действий остается без изменений (см. Методические пособия к 1-ой и 2-ой Лабораторным работам).

Индивидуальные задания:

Вариант № 1.

Фирма набирает штат сотрудников и располагает 4 группами различных должностей, а в каждой группе 5, 3, 6, 4 вакансий. Кандидаты на должность проходят тестирование, по результатам которого их разделяют на 3 группы, по 7, 5, 6 человек в каждой группе. Для каждого кандидата отобранных в i-ю группу требуются определенные затраты c_ij, долл. на обучение для занятия должности в j-ой группе

Необходимо распределить кандидатов на должности, затратив минимальные средства на их обучение.

Вариант № 2.

Фирма набирает штат сотрудников и располагает 4 группами различных должностей, а в каждой группе 15, 8, 11, 10 вакансий. Кандидаты на должность проходят тестирование, по результатам которого их разделяют на 3 группы, по 23, 9, 12 человек в каждой группе. Для каждого кандидата отобранных в i-ю группу требуются определенные затраты c_ij, долл. на обучение для занятия должности в j-ой группе

Необходимо распределить кандидатов на должности, затратив минимальные средства на их обучение.

Вариант № 3.

Для перевозки пассажиров по трем маршрутам аэропорт располагает тремя типами самолетов. Вместимость самолета i-го типа, i = 1, 2, 3, равна 150, 200 и 300 пассажиров соответственно, а потребность в перевозке пассажиров по j-му маршруту, j = 1, 2, 3, за сезон составляет соответственно 5600, 7000 и 6500 человек. Эксплуатационные расходы самолета i-го типа на j-ом маршруте равны c_ij денежных единиц и представлены матрицей

.

Парк самолетов каждого типа составляет 35, 38 и 25 единиц соответственно.

Определить сколько самолетов каждого типа ис пользовать на каждом из маршрутов, чтобы затраты на перевозку пассажиров были минимальными.

Вариант №4.

Требуется распределить самолеты трех типов по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний соответственно не менее 300, 200, 900 и 600 ед. груза.

Тип самолета	Число самолетов	Месячный объем перевозок одним самолетом по авиалиниям
		1	2	3	4
1	40	15	10	20	50
2	25	30	20	10	17
3	30	25	50	30	45

Матрица эксплуатационных расходов на один рейс по каждому маршруту, долл. имеет вид

.

Вариант №5.

Необходимо распределить самолеты трех типов по четырем авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний соответственно не менее 300, 200, 1000 и 500 ед. груза.

Тип самолета	Число самолетов	Месячный объем перевозок одним самолетом по авиалиниям
		1	2	3	4
1	50	15	10	20	50
2	20	30	25	10	17
3	30	25	50	30	45

Матрица эксплуатационных расходов на один рейс по каждому маршруту, долл. имеет вид

.

Вариант №6.

Частный инвестор решил вложить 500 тыс. руб. в различные ценные бумаги. После консультации со специалистами фондового рынка он выбрал для размещения своих средств три типа акций и два типа государственных облигаций, а часть денег решил положить на срочный вклад в банк (см. таблицу).

Вложение	Доход, %	Риск
Акции А	15	Высокий
Акции В	12	Средний
Акции С	9	Низкий
Гос. облигации: долгосрочные краткосрочные	11 8	– –
Срочный вклад в банке	6	–

Инвестор выдвигает следующие условия:

– все 500 тыс. руб. должны быть инвестированы,

– по крайней мере 100 тыс. руб. должны быть на срочном вкладе в банке.

– по крайней мере 25% средств, инвестированных в акции, должны быть инвестированы в акции с низким риском

– в облигации нужно инвестировать по крайней мере столько же, сколько в акции

– не более 125 тыс. руб. должно быть вложено в бумаги с доходом менее 10%.

Определить портфель бумаг инвестора, удовлетворяющий всем требованиям и максимизирующий годовой доход.

Вариант №7.

Большой универсальный магазин собирается заказать новую коллекцию костюмов для весеннего сезона. Решено заказать четыре типа костюмов, из которых три – массового спроса, и один тип – дорогие импортные костюмы. Средние затраты рабочего времени продавцов на продажу одного костюма каждого типа, объем затрат на рекламу, площади, в расчете на один костюм каждого и прибыль от реализации одного костюма каждого типа приведены в таблице

Тип костюма		Прибыль, долл	Время, час	Реклама, у.е.	Площадь, кв.м.
Костюмы массового спроса	Типа 1 2 3	35 47 30	0,4 0,5 0,3	2 4 3	1,00 1,50 1,25
Импортные костюмы		90	1,0	9	3,00

Предполагается, что весенний сезон будет длиться 90 дней. Магазин открыт 10 час. в день, 7 дн. в неделю. В отделе костюмов постоянно будут два продавца, площадь, выделенная на отдел костюмов составляет 6000 кв.м. На рекламу всех костюмов отпущено 15 тыс. у.е.

Определить сколько костюмов каждого типа необходимо закупить для дальнейшей их продажи в магазине, чтобы полученная прибыль была максимальной?

Вариант 8.

Управляющему банка представлены 4 проекта, претендующие на получение кредита в банке. Доступная наличность в банке, потребности проектов в денежных средствах по периодам (например, квартал) и прибыль, ожидаемая от реализации каждого проекта приведены в таблице

Проект	Потребность в денежных средствах по периодам реализации проекта				Прибыль
	1	2	3	4
A	8	8	10	10	21
B	7	9	9	11	18
C	5	7	9	11	16
D	9	8	7	6	17,5
Доступная наличность в банке по периодам	22	25	38	30

При оценке этих предложений принять во внимание потребность проектов в денежных средствах и доступную банку наличность по соответствующим периодам.

Управляющему банком необходимо определить какие проекты следует финансировать и какие средства для этого требуются в течение каждого периода, чтобы суммарная прибыль от реализации проектор была максимальной?

Вариант №9.

Фирма планирует провести рекламную кампанию нового продукта в шести популярных журналах и для этой цели ассигнует 120 тыс. руб.

Фирма полагает, что для эффективности рекламы необходимо, чтобы реклама прошла в каждом журнале не менее шести раз и общий тираж рекламных объявлений должен составить не менее 800 млн. экземпляров. Стоимость размещения одного рекламного объявления в каждом журнале и тираж каждого журнала приведены в таблице

№ издания	Стоимость размещения рекламы в одном выпуске журнала, руб.	Тираж одного выпуска журнала, млн. экз.
1	1474,2	9,9
2	1244,1	8,4
3	1131,0	8,2
4	700,7	5,1
5	530,0	3,7
6	524,4	3,6

Составить план выпуска рекламы с минимальными издержками, при условии, что на рекламу в любом журнале может быть истрачено не более трети отпущенной суммы, а общая стоимость рекламы в третьем и четвертом журналах не должна превышать 75 тыс. руб.

Вариант №10.

Фирма намеревается рекламировать свою продукцию на телевидении, радио, в газетах и посредством расклейки цветных афиш. Из предыдущего опыта менеджер по маркетингу фирмы знает, что размещение рекламы каждым из указанных способов приводит к увеличению прибыли от продаж примерно на 10, 3, 7 и 4 у.е. на каждую единицу у.е., вложенную в рекламу.

Суммарные средства, ассигнуемые фирмой составляют 500 тыс. у.е., причем из них на телевидение и афиши фирма планирует затратить не более 40% и 20% соответственно. Учитывая огромную армию автомобилистов, слушающих в дороге радио, фирма планирует израсходовать на этот вид рекламы по крайней мере половину средств, отводимых телевидению.

Необходимо так распределить средства на все виды рекламы, чтобы ожидаемое от рекламы увеличение продаж было максимальным.

Вариант №11.

Мясокомбинат имеет в своем составе четыре завода, на каждом из которых может изготавливаться три вида колбасных изделий. Мощности каждого из заводов соответственно равны 320, 280, 270 и 350 т/сут. Ежедневные потребности в колбасных изделиях каждого вида также известны и соответственно равны 450, 370 и 400 т. Зная себестоимость 1 т каждого вида колбас на каждом заводе, которые определяются матрицей

.

Найти такое распределение выпуска колбасных изделий между заводами, при котором себестоимость изготавливаемой продукции является минимальной.

Вариант №12.

Морское судно грузоподъемностью 20 тыс. т. и вместимостью 28 тыс. куб.м. может быть использовано для перевозки пяти видов грузов. Данные о массе, объеме и стоимости единицы груза каждого вида приведены в таблице

Параметры единицы груза	Номер груза
	1	2	3	4	5
Масса, т	95	70	90	105	75
Объем, куб.м	125	90	110	100	120
Стоимость, млн.руб.	270	280	440	350	400

Определить, сколько единиц груза каждого вида следует загрузить на судно, чтобы суммарная стоимость груза была максимальной и выполнялись ограничения по вместимости и грузоподъемности судна.

Вариант №13.

Пароход может быть использован для перевозки 11 наименований грузов. Масса, объем и цена единицы каждого наименования груза приведены в таблице

Параметры груза	Номер груза
	1	2	3	4	5	6	7	8	9	10	11
Масса, т	80	62	92	82	90	60	81	83	86	65	83
Объем, куб.м	100	90	96	110	120	80	114	60	106	114	86
Цена, тыс.руб.	4,4	2,7	3,2	2,8	2,7	2,8	3,3	3,5	4,7	3,9	4,0

На пароход может быть погружено не более 800т груза общим объемом, не превышающим 600 куб.м. Определить, сколько единиц каждого груза следует поместить на пароход так, чтобы общая стоимость размещенного груза была максимальной.

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высш. Шк., 1986

2. Костевич Л.С. Математическое программирование: Информ. технологии оптимальных решений. – Мн.: Новое знание, 2003

3. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вуз. Учебник, 2004